package com.example.question.tree.tree3;

/**
 * 不同的二叉树搜索树
 */
public class Code18_96 {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        return numTrees(n, dp);
    }

    public int numTrees(int n, int[] dp) {
        //如果只有0，或者1个节点，则可能的子树情况为1种
        if (n == 0 || n == 1) {
            return 1;
        }

        int count = 0;
        for (int i = 1; i <= n; i++) {

            //当用i这个节点当做根节点时
            int leftNum;
            //左边有多少种子树
            if (dp[i - 1] == 0) {
                dp[i - 1] = numTrees(i - 1, dp);
            }
            leftNum = dp[i - 1];

            //右边有多少种子树
            int rightNum;
            if (dp[n - i] == 0) {
                dp[n - i] = numTrees(n - i, dp);
            }
            rightNum = dp[n - i];

            //乘起来就是当前节点的子树个数
            count += leftNum * rightNum;
        }

        return count;
    }
}
